package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式转后缀表达式
 * @Auther Jun jie Yi
 * @Date 20:11 2021/7/10
 */
public class InfixToSuffix {
    public static void main(String[] args) {
        String str = "1+((22+3)*4)-5";
        List<String> ls = parseSuffixExpressionList(toInfixExpressionList(str));
        System.out.println(ls);
        int res = PolandNotation.calculate(ls); //调用计算后缀表达式的方法
        System.out.println(res);
    }

    //得到一个后缀表达式的字符串
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //定义两个栈
        Stack<String> s1 = new Stack<>(); //符号栈
        //Stack<String> s2 = new Stack<>(); //这里最终求的是逆序的不用特意定义一个栈
        List<String> s2 = new ArrayList<>();
        //遍历 ls
        for (String e: ls) {
            //如果是一个数就入栈
            if(e.matches("\\d+")) {
                s2.add(e);
            } else if(e.equals("(")) { //如果是一个 ( 直接入栈
                s1.push(e);
            } else if(e.equals(")")) { //如果是一个 ) 依次将 ( 之前的运算符弹出入栈，最后还要弹出 (
                while(!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop(); //消掉最后的 (
            } else {
                //当 e 的优先级 <= s1 栈顶运算符，将 s1 栈顶的的运算符弹出加入到 s2 中，重复这个工作
                while(s1.size() != 0 && getValue(s1.peek()) >= getValue(e)) { //栈顶元素的优先级 >= 当前元素的优先级
                    s2.add(s1.pop());
                }
                s1.push(e); //将需要将 e 加入栈
            }
        }
        //将 s1 中剩余的运算符加入到 s2 中
        while(!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        //返回结果
        return s2;
    }

    //将中缀表达式转化为对应的 List (这里主要是多位数字的时候需要处理)
    public static List<String> toInfixExpressionList(String s) {
        List<String> ls = new ArrayList<>();
        int i = 0;
        String str;
        char c;
        do {
            //如果 c 是一个非数字就加入到 ls
            if((c = s.charAt(i)) < 48 || (c = s.charAt(i) )> 57) {
                ls.add(c + "");
                i++;
            } else {
            //如果是一个数字(多位数的时候要将后面的数字拼接上去)
                str = "";
                while(i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        } while(i < s.length());
        return ls;
    }

    //获取每个符号对应的优先级
    public static int getValue(String operation) {
        int res = 0;
        if("+".equals(operation) || "-".equals(operation)) {
            res = 1;
        } else if("*".equals(operation) || "/".equals(operation)) {
            res =  2;
        } else if("(".equals(operation)){
            res = 0;
        } else {
            System.out.println("运算符不正确");
        }
        return res;
    }
}
